#include "tree.h"


#define NULL ((void*)0)
void TNRemove(tnode* snode)
{
    if(snode->par != NULL) return;
    tnode* from = snode->par;
    snode->par = NULL;
	tnode* buff = from->son;
	if(buff == snode) // 删亲生儿子的节奏
	{
		if(buff -> bro == NULL)
		{//这儿子还是独生子女
			from->son =NULL;
		}
		else
		{//不是独生子女
			from->son = buff;
		}
	}
	else //删儿子的某个兄弟
	{
		while(buff->bro != snode)
		{
			buff =buff->bro;
		}
		buff->bro = snode->bro;
	}

}
void TNInsert(tnode* from,tnode* snode)
{
	if(from->son == NULL) //还没儿子啊
	{
		from->son = snode;
		snode->par = from;
	}
	else
	{
		tnode* buff = from->son;
		while(buff->bro != NULL)
		{
			buff = buff->bro;
		}
		buff->bro = snode;
        snode->par = from;
	}
}
tnode* TNDeepFind(tnode* root,void* target)
{//找起来还是很累的，得遍历
//因为内存初始化问题 用stack做
	stack path;
	unsigned int base[256];
	StackInit(&path,base,sizeof(tnode*),256);
	StackPush(&path,&root);
	tnode* pointer = root;
	while(StackEmpty(&path) != 0)
	{
	//on check
		if(pointer->son != NULL)
		{
			if(pointer->son->mark == target) return pointer->son;
			tnode* buff = pointer->son;
			while(buff->bro != NULL)
			{
				buff = buff->bro;
				if(buff->mark == target) return buff;
			}
		}
	//on explore
		if(pointer != NULL)
		{
			if(pointer->son != NULL)
			{
				StackPush(&path,&pointer);
				pointer = pointer->son;
			}
			else
			{
				pointer = pointer->bro;
			}
		}
		else
		{
			StackPop(&path,&pointer);
			pointer = pointer->bro;
		}
	}
    return NULL;

}

tnode* TNWideFind(tnode* root,void* mark)
{
    queue path;
	unsigned int base[256];
    QueueInit(&path,base,sizeof(tnode*),256);
    QueuePush(&path,&root);
    while(!QueueEmpty(&path))
    {
        tnode* buff;
        QueuePop(&path,&buff);
        if(buff->mark == mark) return buff;
        if(buff->son != NULL)
        {
            QueuePush(&path,&buff->son);
            buff = buff->son;
            while(buff->bro != NULL)
            {
                QueuePush(&path,&buff->bro);
                buff = buff->bro;
            }
        }
    }
    return NULL;
}
